"""
水桶排列组合问题解决方案

问题描述：
1. 有n个颜色各不相同的水桶，桶身和桶盖颜色相同
2. 将桶身和桶盖拆分并随机打乱，需要找出所有可能的组合
3. 进阶：N个不同大小水桶，每个桶有不同重量，找出最重和最轻的桶排列
"""


def generate_permutations(items):
    """
    生成给定项目的全排列（不使用内置排列函数）
    
    Args:
        items: 要排列的项目列表
    
    Returns:
        所有排列的列表
    """
    # 基本情况：如果只有一个元素，则只有一种排列
    if len(items) <= 1:
        return [items]
    
    # 递归情况：对于每个元素，将其作为第一个元素，
    # 然后对剩余元素生成所有排列
    result = []
    for i in range(len(items)):
        # 取出当前元素
        current = items[i]
        # 获取剩余元素
        remaining = items[:i] + items[i+1:]
        # 生成剩余元素的所有排列
        for perm in generate_permutations(remaining):
            # 将当前元素添加到每个排列的开头
            result.append([current] + perm)
    
    return result


def solve_bucket_combination_problem(n):
    """
    解决基础的水桶组合问题
    
    Args:
        n: 水桶的数量
    
    Returns:
        所有可能的桶身和桶盖组合
    """
    # 创建桶身和桶盖列表（用数字代表不同颜色）
    buckets = list(range(1, n+1))
    
    # 生成所有可能的排列（桶盖的排列）
    lid_permutations = generate_permutations(buckets)
    
    # 每个排列代表一种组合方式
    combinations = []
    for i, lids in enumerate(lid_permutations):
        combination = list(zip(buckets, lids))
        combinations.append(combination)
    
    return combinations


def calculate_total_weight(arrangement, weights):
    """
    计算特定排列的总重量
    
    Args:
        arrangement: 桶的排列
        weights: 每个桶的重量映射
    
    Returns:
        总重量
    """
    total = 0
    for bucket in arrangement:
        total += weights[bucket]
    return total


def solve_weighted_bucket_problem(buckets, weights):
    """
    解决加权水桶问题，找出最重和最轻的排列
    
    Args:
        buckets: 桶的列表
        weights: 每个桶的重量字典
    
    Returns:
        (最轻排列, 最重排列, 最轻重量, 最重重量)
    """
    # 生成所有排列
    all_arrangements = generate_permutations(buckets)
    
    # 初始化最轻和最重排列
    lightest_arrangement = None
    heaviest_arrangement = None
    min_weight = float('inf')
    max_weight = float('-inf')
    
    # 遍历所有排列，找出最轻和最重的
    for arrangement in all_arrangements:
        weight = calculate_total_weight(arrangement, weights)
        if weight < min_weight:
            min_weight = weight
            lightest_arrangement = arrangement
        if weight > max_weight:
            max_weight = weight
            heaviest_arrangement = arrangement
    
    return lightest_arrangement, heaviest_arrangement, min_weight, max_weight


def analyze_complexity():
    """
    分析算法复杂度
    """
    analysis = """
    基础水桶组合问题复杂度分析：
    
    时间复杂度：
    - 生成全排列的递归函数时间复杂度为 O(n!)
    - 对于每个排列，我们需要创建一个组合，时间复杂度为 O(n)
    - 因此总时间复杂度为 O(n × n!)
    
    空间复杂度：
    - 递归调用栈的深度为 O(n)
    - 存储所有排列需要 O(n! × n) 的空间
    - 因此总空间复杂度为 O(n! × n)
    
    加权水桶问题复杂度分析：
    
    时间复杂度：
    - 生成全排列：O(n!)
    - 计算每个排列的重量：O(n) 
    - 遍历所有排列找最值：O(n! × n)
    - 因此总时间复杂度为 O(n! × n)
    
    空间复杂度：
    - 与基础问题相同，为 O(n! × n)
    """
    return analysis


if __name__ == "__main__":
    # 示例1：基础水桶组合问题
    print("=== 基础水桶组合问题 ===")
    n = 3
    combinations = solve_bucket_combination_problem(n)
    print(f"当 n = {n} 时，所有可能的组合为：")
    for i, combo in enumerate(combinations):
        print(f"组合 {i+1}: {combo}")
    
    print("\n=== 加权水桶问题 ===")
    # 示例2：加权水桶问题
    buckets = [1, 2, 3]
    weights = {1: 10, 2: 20, 3: 15}  # 每个桶的重量
    lightest, heaviest, min_w, max_w = solve_weighted_bucket_problem(buckets, weights)
    print(f"桶列表: {buckets}")
    print(f"桶重量: {weights}")
    print(f"最轻排列: {lightest}, 重量: {min_w}")
    print(f"最重排列: {heaviest}, 重量: {max_w}")
    
    print("\n=== 复杂度分析 ===")
    print(analyze_complexity())